package dp;

import java.util.HashMap;
import java.util.Map;

public class P467 {
    public int findSubstringInWraproundString2(String p) {
        if (p == null || p.length() == 0) {
            return 0;
        } else if (p.length() == 1) {
            return 1;
        }
        int total = 0;
        //
        Map<String, String> map = new HashMap<>();
        char[] letters = p.toCharArray();
        for (int len = 1; len <= p.length(); len++) {
            for (int i = 0; i <= p.length() - len; i++) {
                int prev = letters[i] - 'a';
                boolean flag = true;
                for (int j = 1; j < len; j++) {
                    int next = letters[i + j] - 'a';
                    if ((prev + 1) % 26 != next) {
                        flag = false;
                        break;
                    }
                    prev = next;
                }
                String key = p.substring(i, i + len);
                if (flag && !map.containsKey(key)) {
                    map.put(key, "");
                    total += 1;
                }
            }
        }
        return total;
    }


    public int dp(String p) {
        int len = p.length();
        boolean[][] dp = new boolean[len][len];
        Map<String, String> memMap = new HashMap<>();
        //
        int total = 0;
        //1. 初始化
        for (int i = 0; i < len; i++) {
            String sub = p.substring(i, i + 1);
            dp[i][i] = true;
            if (!memMap.containsKey(sub)) {
                memMap.put(sub, "");
                total += 1;
            }
        }
        //2. 填值
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < len - i; j++) {
                if (dp[j][j + i - 1]) {
                    int pre = p.charAt(j + i - 1) - 'a';
                    int now = p.charAt(j + i) - 'a';
                    if (now - pre == 1 || now - pre == -25) {
                        dp[j][j + i] = true;
                        String sub = p.substring(j, i + j + 1);
                        if (!memMap.containsKey(sub)) {
                            memMap.put(sub, "");
                            total += 1;
                        }
                    } else {
                        dp[j][j + i] = false;
                    }
                } else {
                    dp[j][j + i] = false;
                }
            }
        }
        return total;
    }

    public int findSubstringInWraproundString(String p) {
        // 记录 p 中以每个字符结尾的最长连续子串的长度
        int[] dp = new int[26];
        char[] array = p.toCharArray();
        // 记录当前连续子串的长度
        int count = 0;
        // 遍历 p 中的所有字符
        for (int i = 0; i < array.length; i++) {
            // 判断字符是否连续
            if (i > 0 && (array[i] - array[i - 1] - 1) % 26 == 0) {
                // 连续则自加
                count++;
            } else {
                // 不连续则刷新
                count = 1;
            }
            // 只存储最长的连续长度
            dp[array[i] - 'a'] = Math.max(dp[array[i] - 'a'], count);
        }
        int result = 0;
        // 统计所有以每个字符结尾的最长连续子串的长度，就是唯一相等子串的个数
        for (int i : dp) {
            result += i;
        }
        return result;
    }

    public static void main(String[] args) {
        String s = "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz";
        int count = new P467().findSubstringInWraproundString(s);
        System.out.println(count);
    }
}
